package simple;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/2/8 23:14
 */
public class No448_找到所有数组中消失的数字 {
    public static void main(String[] args) {
        Solution448 solution448 = new Solution448();
        int[] data = new int[]{4, 2, 7, 8, 6, 6, 1, 3};
        List<Integer> disappearedNumbers = solution448.findDisappearedNumbers(data);
        System.out.println();
    }
}

class Solution448 {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // 原地归位
        // 1 ≤ a[i] ≤ n -> 0 +1≤ a[i] ≤ n - 1+1 -> 索引
        //当a[i]值为x的时候,归位于索引x-1
        //当归位的地方数值小于0,直接不用处理
        for (int num : nums) {
            //num:-3 -> 3 ,归位索引2位置
            //判断归位的位置数字是不是大于0,如果不是,跳过
            if (nums[Math.abs(num) - 1] > 0) {
                nums[Math.abs(num) - 1] = -nums[Math.abs(num) - 1];
            }
        }

        List<Integer> list = new ArrayList<>();

        //找到没有修改的数,添加入值即可
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                //说明没有被修改,说明该位置没有归位
                //说明缺失
                list.add(i + 1);
            }
        }
        return list;
    }
}



    //public List<Integer> findDisappearedNumbers(int[] nums) {
    //    //排序查漏法
    //    //排序
    //    Arrays.sort(nums);
    //    List<Integer> list = new ArrayList<>();
    //    if (nums.length == 0) {
    //        return list;
    //    }
    //
    //    //1.缺尾
    //    int red = nums[nums.length - 1];
    //    int green = nums.length;
    //    //补尾
    //    for (int i = red + 1; i <= green; i++) {
    //        list.add(i);
    //    }
    //
    //    //2.缺头
    //    red = 1;
    //    green = nums[0];
    //    //补头
    //    for (int i = 1; i <= green - 1; i++) {
    //        list.add(i);
    //    }
    //
    //    //3.缺中间
    //    for (int i = 0; i < nums.length - 1; i++) {
    //        if (nums[i + 1] - nums[i] > 1) {
    //            //跳跃
    //            red = nums[i];
    //            green = nums[i + 1];
    //            //补
    //            for (int j = red + 1; j <= green - 1; j++) {
    //                list.add(j);
    //            }
    //        }
    //    }
    //    return list;
    //}



    //public List<Integer> findDisappearedNumbers(int[] nums) {
    //    //1 ≤ a[i] ≤ n
    //    //[1,2,3,3,5] -> [4]
    //    //[2,3,4,5,5] -> [1]
    //    //[2,2,4,4,1]-> [3,5]
    //
    //    //哈希法,简单算法
    //    Set<Integer> set = new HashSet<>();
    //    //对nums进行去重
    //    //[2,2,4,4,1] -> [2,4,1]
    //    for (int num : nums) {
    //        set.add(num);
    //    }
    //
    //    //拿出补全后的数[1,2,3,4,5]
    //
    //    List<Integer> list = new ArrayList<>();
    //
    //    for (int i = 1; i <= nums.length; i++) {
    //        //找到不存在的数
    //        if (!set.contains(i)) {
    //            //list加入
    //            list.add(i);
    //        }
    //    }
    //    return list;
    //}
